// 中序遍历： 左-根-右
function inorderTraversal(root) {
    if (!root) return [];

    let res = [], stack = [];

    while (stack.length || root) {
        while (root) {
            stack.push(root);
            root = root.left;
        };

        root = stack.pop();
        res.push(root.val);
        root = root.right;
    };
    return res;
};


// test
const root = {
    val: 1,
    right: {
        val: 2,
        left: {
            val: 3,
        },
    },
};

const res = inorderTraversal(root);
 
console.log(res);   // [ 1, 3, 2 ]